#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

void sbSort(const double* Data, int n, double *data)
{
	memcpy(data, Data, sizeof(double)*n);
	for (int i = 0; i < n-1; i++)
		for (int j = i + 1; j < n; j++)
			if ( data[i] > data[j] )
			{
				double temp = data[i];
				data[i] = data[j] ;
				data[j] = temp;
			}

}

void findKthMin(const double* Data, int n, int K,
			   double* value, int* index)
{
	double* data = new double [n];
	memcpy(data, Data, sizeof(double)*n);
	bool flag = false;
	int k = K;
	int low = 0;
	int high = n - 1;
	while ( !flag )
	{
		double key = data[low];
		int x = low;
		int y = high;
		while ( x < y )
		{
			while( key <= data[y] && x < y) y--;
			data[x] = data[y];
			while( data[x] <= key && x < y) x++;
			data[y] = data[x];
		}
		data[x] = key;
		int cnt = x - low + 1;
		if (k == cnt ) flag = true;
		if ( k > cnt ) { k = k - cnt; low = x + 1;} 
		else { high = x - 1; }
	}
	*value = data[ K -1 ];
	//linear search for index
	for(int i = 0; i < n; i++)
		if (abs(Data[i] - *value) < 1e-8) *index = i;
	delete [] data;
}

void findKthMin2(const double* data, int n,int K,
				 int* id)
{
	for (int i = 0; i < n; i++)
		id[i] = i;
	bool flag = false;
	int k = K;
	int low = 0;
	int high = n - 1;
	while ( !flag )
	{
		int key = id[low];
		int x = low;
		int y = high;
  		while ( x < y )
		{
			while( data[key] <= data[id[y]] && x < y) y--;
			id[x] = id[y];
			while( data[id[x]] <= data[key] && x < y) x++;
			id[y] = id[x];
		}
		id[x] = key;
		int cnt = x - low + 1;
		if (k == cnt ) flag = true;
		if ( k > cnt ) { k = k - cnt; low = x + 1;} 
		else { high = x - 1; }
	}
	
}

void test_2_Accuracy()
{
	//double a[] = {5,4,3,7,2,1,8,9,6};
	//int n = 9;
	//int K = 6;
	//int* index = new int [n];

	//for (int j = 0; j < 9; j++){
	//	K = j+1;
	//findKthMin2(a,n,K,index);
	//	for (int i = 0; i < K; i++)
	//	cout<<a[index[i]]<<" ";
	//cout<<endl;
	//}
	srand(time(0));
	int n = 1000000;
	int* id = new int [n];
	double *a = new double [n];
	double *b = new double [n];
	for (int i = 0; i < n; i++)
	a[i] = (double)rand() / RAND_MAX * 100;

	double val;
	int index;
	for (int K = 1; K < 50; K++)
	{
		findKthMin(a,n,K,&val,&index);
		findKthMin2(a,n,K,id);
		for (int i = 0; i < K; i++)
			if (a[id[i]] > val || (a[id[K-1]] - val)>1e-6)
				cout<<"false"<<endl;
	}
}

void test_Accuracy()
{
	srand(time(0));
	int n = 1000;
	double *a = new double [n];
	double *b = new double [n];
	for (int k = 0; k < 100; k++)
	{
	for (int i = 0; i < n; i++)
		a[i] = (double)rand() / RAND_MAX * 100;
	sbSort(a, n, b);
	double val;
	int index;
	double s = 0;
	for (int i = 0; i < n; i++)
	{
		findKthMin(a, n, i+1, &val, &index);
		s += abs(val - b[i]);
	}
	cout<<k<<" "<<s<<endl;
	if ( s > 0.00001 ) 
		cout<<"fail"<<endl;
	}
	delete [] a;
	delete [] b;
}

void test_Speed()
{
	int n = 10000000;
	double* a = new double [n];
	double s = 0;
	for (int i = 0; i < 100; i++)
	{
		int K = 500;
		for (int j = 0; i < n; i++)
				a[i] = (double)rand()/RAND_MAX * 10;
		double val;
		int index;
		clock_t start = clock();
		findKthMin(a, n, K, &val, &index);
		clock_t finish = clock();
		s+= (double)finish - (double)start;
	}
	cout<<s/100<<endl;
}

void test_2_Speed()
{
	int n = 10000000;
	double* a = new double [n];
	double s = 0;
	int* id = new int [n];
	for (int i = 0; i < 100; i++)
	{
		int K = 50;
		for (int j = 0; i < n; i++)
			a[i] = (double)rand()/RAND_MAX * 10;
		clock_t start = clock();
		findKthMin2(a,n,K,id);
		clock_t finish = clock();
		s += (double)finish - (double)start;
	}
	cout<<s/100<<endl;
} 
int main()
{
	test_2_Speed();
	system("pause");
	return 0;
}